let obj = {
  value: 1,
  children: [
    {
      value: 2,
      children: [
        {
          value: 4,
          children: [
            {
              value: 8
            },
            {
              value: 9
            }
          ]
        },
        {
          value: 5
        }]
    },
    {
      value: 3,
      children: [
        {
          value: 6
        },
        {
          value: 7
        }]
    }
  ]
}
// 深度优先
console.log("深度优先遍历")
function walk (obj) {
  console.log(obj.value)
  if (obj.children) {
    obj.children.forEach(item => {
      walk(item)
    })
  }
}
walk(obj)
console.log("广度优先遍历")
// 广度优先
let arr = [obj]
let tempParam = []
function walkWidly (arr) {
  let tempParam = []
  arr.forEach(item => {
    console.log(item.value)
    if (item.children) {
      // 拼接下一次迭代调用的数组
      tempParam = tempParam.concat(item.children)
    }
  })
  if (tempParam.length) walkWidly(tempParam)
}
walkWidly(arr)
// 广度优先(写法2)
// 队列: 先进先出
// 利用数组的shift()方法模拟出队, 每次遍历使用push方法模拟入队操作
function walkWidlyBetter (arr) {
  while (arr.length) {
    let temp = arr.shift()
    console.log(temp.value)
    if (temp.children) {
      temp.children.forEach(item => {
        arr.push(item)
      })
    }
  }
}
console.log("广度优先遍历(改进版)")
walkWidlyBetter(arr)
